﻿#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <numeric>

using namespace std;

//172. 阶乘后的零
//给定一个整数 n ，返回 n!结果中尾随零的数量。
//提示 n!= n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
//示例 1：
//输入：n = 3
//输出：0
//解释：3!= 6 ，不含尾随 0
class Solution1 {
public:
    int trailingZeroes(int n) {
        // 所有阶乘产生的末尾0都是通过 5 * 2得到的
        // 所以 n! = pow(5, x) * pow(2, y) * α
        // 其中x <= y，α = n! / (pow(5, x) * pow(2, y))，α不以0为结尾
        // 题目中所求的尾随0的数量就是 x
        // n! = ∏i = (∏(5*j)) * β
        // 其中 i 从 1 到 n，j 从1 到 n / 5
        // 但是由于 j 连乘的过程中有可能取到5的倍数
        // 所以尾随0的数量等于 n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
};

//384. 打乱数组
//给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
//实现 Solution class :
//Solution(int[] nums) 使用整数数组 nums 初始化对象
//int[] reset() 重设数组到它的初始状态并返回
//int[] shuffle() 返回数组随机打乱后的结果
//示例 1：
//输入
//["Solution", "shuffle", "reset", "shuffle"]
//[[[1, 2, 3]], [], [], []]
//输出
//[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
//解释
//Solution solution = new Solution([1, 2, 3]);
//solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
//solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
//solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
class Solution2 {
private:
    vector<int> _nums;
public:
    Solution2(vector<int>& nums) {
        // srand(nullptr);
        _nums = nums;
    }

    vector<int> reset() {
        return _nums;
    }

    vector<int> shuffle() {
        vector<int> snums(_nums);
        int n = snums.size();
        for (int i = 0; i < n; ++i) {
            // 抽样不放回，每次则每个数放到i位置的概率为 1 / n
            swap(snums[i], snums[i + rand() % (n - i)]);
        }
        return snums;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */

 // ​382. 链表随机节点  384. 打乱数组
 // 398. 随机数索引  ​528. 按权重随机选择 这几个题都是随机分布的典型例题
//528. 按权重随机选择
//给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。
//请你实现一个函数 pickIndex ，
//它可以 随机地 从范围[0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。
//例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25 % ），
//而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75 % ）。
//示例 2：
//输入：
//["Solution", "pickIndex", "pickIndex", "pickIndex", "pickIndex", "pickIndex"]
//[[[1, 3]], [], [], [], [], []]
//输出：
//[null, 1, 1, 1, 1, 0]
//解释：
//Solution solution = new Solution([1, 3]);
//solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
//solution.pickIndex(); // 返回 1
//solution.pickIndex(); // 返回 1
//solution.pickIndex(); // 返回 1
//solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
//由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
//[null, 1, 1, 1, 1, 0]
//[null, 1, 1, 1, 1, 1]
//[null, 1, 1, 1, 0, 0]
//[null, 1, 1, 1, 0, 1]
//[null, 1, 0, 1, 0, 0]
//......
//诸若此类。
class Solution3 {
    vector<int> _weight;
public:
    Solution3(vector<int> w) {
        _weight = move(w);
        partial_sum(_weight.begin(), _weight.end(), _weight.begin());
    }

    int pickIndex() {
        int sum = _weight.back();
        int randnum = rand() % sum + 1;
        return lower_bound(_weight.begin(), _weight.end(), randnum) - _weight.begin();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */
